#include <assert.h>
#include <unistd.h>

#include <gr_graph_fun.h>
#include "perror_exit.h"

#include "getopt.h"
#include "fuzzycluster.h"
#include "utility.h"

#ifdef HAVE_CONFIG_H
# include "config.h"
#endif

#ifdef DMALLOC
# include "dmalloc.h"
#endif

void
findClustersInConnectedComponent(GraphFrame *component, options *fc_opts)
{
	unsigned int vertex_count;
	LNode_type *ptr;
	
	vertex_count = component->count_vertex;

	/* 
	 * Return if the cluster is tiny 
	 */
	if(vertex_count  < fc_opts->min_cluster_size)
		return;

	/* 
	 * Reduce the graph size by cutting the graph 
	 * about big page rank nodes 
	 */
	else if(vertex_count > fc_opts->max_cluster_size) {
		
		/* Ignore vertices with high page rank */
		compute_rank(component,DEFAULT_PAGE_RANK_ITERATIONS);
		select_big_rank(component,fc_opts->page_rank_ignore);

		/* Recurse */
		findClusters(component,fc_opts);
	}
	
	/* 
	 * The component is a cluster !!!
	 */
	else {
		LNode_type *ptr;
		char *filename;
		unsigned long ecount = 0;
		unsigned long node_count = 0;
		double coefficient;
		char clusterstr[32];

		/* update stats */
		ecount = edge_count(component);
		node_count = component->count_vertex;
		coefficient = ((double)ecount/(double)(node_count * (node_count-1)));
		
		++(fc_opts->stats.cluster_count);
		fc_opts->stats.coefficient_sum += coefficient;

		/* Reset the cluster for each selected vertex to NULL */
		for(ptr = component->list_sel_vertex->back; ptr != component->list_sel_vertex; ptr=ptr->back)
			((PNODE)(ptr->info))->context = NULL;

		insertSelectedNodes(component,fc_opts->addIter);

		/*  Set the cluster attribute for each node in the cluster */
		snprintf(clusterstr,32,"%d",fc_opts->stats.cluster_count);
		for(ptr=component->list_vertices->back; ptr != component->list_vertices; ptr=ptr->back)
			add_attribute((PNODE)(ptr->info),"cluster",clusterstr);

		if(fc_opts->debug >= 2) {
			printf(" - Cluster %d\n",fc_opts->stats.cluster_count);
			for(ptr = component->list_vertices->back; ptr != component->list_vertices; ptr=ptr->back) {
				PNODE node;
				node = (PNODE)ptr->info;
				printf(" | %d %s\n",node->num,node->label);
			}
			printf(" *\n");
		}		

	}
}

void
findClusters(GraphFrame *graph, options *fc_opts)
{
	unsigned int conn_comp_count;
	unsigned int i;
	LNode_type *ptr,*eptr;
	LNode_type *nodes_save, *selected_save;
	unsigned long count_vertex;
	static int last_vertex_count = 0;

	LNode_type **clusters;

	assert(graph != NULL);
	assert(fc_opts != NULL);

	/* Compute Connected Components */
	conn_comp_count = cluster_guess(graph, &clusters);

	nodes_save = graph->list_vertices;
	last_vertex_count = graph->count_vertex;
	
	/* Foreach connected component */
	for(i=0;i<conn_comp_count;i++) {

		if(fc_opts->debug >= 2)
			fprintf(stderr,"Inspecting component %d\n",i);

		/* Set the current list of vertices to the ith component */
		graph->list_vertices = clusters[i];
		graph->count_vertex = count_llist(graph->list_vertices);
		
		if(fc_opts->debug >=2)
			fprintf(stderr," (%d nodes, %d edges)\n",graph->count_vertex, count_llist(get_list_elements(graph->Hedge)));

		if(fc_opts->debug >= 3) {
			for(ptr = graph->list_vertices->back; ptr != graph->list_vertices; ptr = ptr->back)
				fprintf(stderr,"%d ",((PNODE)ptr->info)->num);
			fprintf(stderr,"\n");
		}

		/* Find Clusters in the ith connected component */
		findClustersInConnectedComponent(graph,fc_opts);

	}
	
	graph->list_vertices = nodes_save;
	graph->count_vertex = last_vertex_count;
	
}

int
main(int argc, char **argv)
{
	options *fc_opts;
	char o;
	GraphFrame *graph;
	
	struct option opt_long[] = {
		{"version",no_argument,NULL,'v'},
		{"help",no_argument,NULL,'h'},
		{"max-cluster-size",required_argument,NULL,'a'},
		{"min-cluster-size",required_argument,NULL,'i'},
		{"page-rank-ignore",required_argument,NULL,'p'},
		{"add-iter",required_argument,NULL,'t'},
		{"debug",required_argument,NULL,'d'},
		{"prefix",required_argument,NULL,'r'},
		{0,0,0,0}
	};
	
	if(!(fc_opts = (options *)malloc(sizeof(options))))
		perror_exit("malloc (%s:%d)",__FILE__,__LINE__);
	
	/* Set Default Options */
	fc_opts->min_cluster_size =    DEFAULT_MIN_CLUSTER_SIZE;
	fc_opts->max_cluster_size =    DEFAULT_MAX_CLUSTER_SIZE;
	fc_opts->page_rank_ignore =    DEFAULT_NUM_HIGH_PAGE_RANK;
	fc_opts->debug =               DEFAULT_DEBUG_LEVEL;
	fc_opts->prefix =              strdup(DEFAULT_CLUSTER_GRAPH_SAVE_PREFIX);
	fc_opts->graph =               NULL;
	fc_opts->addIter =             99999;

	fc_opts->stats.cluster_count = 0;
	
	while((o = getopt_long(argc,argv,"vha:i:p:d:r:t:",opt_long,NULL)) != EOF) {
		switch(o) {
			case 'v':
				version();
				return EXIT_SUCCESS;
			case 'h':
				help();
				return EXIT_SUCCESS;
			case 'a':
				fc_opts->max_cluster_size = atoi(optarg);
				break;
			case 'i':
				fc_opts->min_cluster_size = atoi(optarg);
				break;
			case 'p':
				fc_opts->page_rank_ignore = atoi(optarg);
				break;
			case 'd':
				fc_opts->debug = atoi(optarg);
				break;
			case 'r':
				fc_opts->prefix = strdup(optarg);
				break;
			case 't':
				fc_opts->addIter = atoi(optarg);
				break;
			case '?':
			default:
				help();
				return EXIT_FAILURE;
		}
	}
	
	if (optind < argc) {
		while (optind < argc) {
			if(fc_opts->graph)
				free(fc_opts->graph);
			fc_opts->graph = strdup(argv[optind++]);
		}
	}
	
	if(!(fc_opts->graph)) {
		help();
		return EXIT_FAILURE;
	}
	
	graph = load_graph(fc_opts->graph);
	
	if(fc_opts->debug >= 1) {
		fprintf(stderr,"  Graph:            %s\n",fc_opts->graph);
		fprintf(stderr,"  Max Cluster Size: %d\n",fc_opts->max_cluster_size);
		fprintf(stderr,"  Min Cluster Size: %d\n",fc_opts->min_cluster_size);
		fprintf(stderr,"  Page Rank Ignore: %d\n",fc_opts->page_rank_ignore);
		fprintf(stderr,"  Cluster Names:    %sn%s\n",fc_opts->prefix,DEFAULT_CLUSTER_GRAPH_SAVE_POSTFIX);
		fprintf(stderr,"\n");
	}

	findClusters(graph,fc_opts);
	
	print_graph(graph);

	if(fc_opts->debug >= 1) {
		fprintf(stderr,"discovered clusters: %d\n",fc_opts->stats.cluster_count);
		fprintf(stderr,"cluster coefficient: %e\n",(double)fc_opts->stats.coefficient_sum/(double)fc_opts->stats.cluster_count);
	}
	
	return EXIT_SUCCESS;
	
}
